#include "graph.hpp"
#include "../utils/utils.hpp"
#include "../structs/binheap.hpp"
#include <limits>
#include <cerrno>


const unsigned int Graph::MaxNode = std::numeric_limits<NodeId>::max();

const unsigned int Graph::MaxPeople = std::numeric_limits<unsigned short>::max();

Graph::Graph(unsigned int n) {
	init(n);
}

Graph::Graph(FILE *in) {
	unsigned int nnodes;
	if (fscanf(in, "nnodes: %u\n", &nnodes) != 1)
		fatal("failed to read the number of nodes");
	if (nnodes > MaxNode)
		fatal("too many nodes, max=%d", MaxNode);

	init(nnodes);

	unsigned int nedges;
	if (fscanf(in, " nedges: %u\n", &nedges) != 1)
		fatal("failed to read the number of edges");

	for (unsigned int i = 0; i < nedges; i++) {
		int src, dst;
		double cost;
		if (fscanf(in, " %d %d %lg", &src, &dst, &cost) != 3)
			fatal("failed to read edge %u (counting from 0)", i);
		if (src < 0 || src >= (int) nnodes)
			fatal("edge %u: %d is an invalid source node (0—%u)", i, src, nnodes);
		if (dst < 0 || dst >= (int) nnodes)
			fatal("edge %u: %d is an invalid destination node (0—%u)", i, dst, nnodes);
		if (cost <= 0)
			fatal("edge %u: %g is an invalid cost, must be positive", i, cost);
		if (cost == std::numeric_limits<double>::infinity())
			fatal("edge %u: invalid (infinite) cost", i);
		addedge(src,dst, cost);
	}

	unsigned int npeople = 0;
	for ( ; ; ) {
		int c = fgetc(in);
		while (isspace(c))
			c = fgetc(in);
		ungetc(c, in);
		if (!isdigit(c))
			break;

		unsigned int p;
		int n;
		int m = fscanf(in, " %u at %d\n", &p, &n);
		if (m < 2) {
			if (m == 1 || ferror(in))
				fatal("failed to read number of people line");
			break;
		}
		if (n < 0 || n >= (int) nnodes)
			fatal("%d is an invalid node (0—%u)", n, nnodes);
		if (nodes[n].p >= 0) {
			people[nodes[n].p].num++;
		} else {
			nodes[n].p = people.size();
			people.push_back(People(p, n));
		}
		if (npeople >= MaxPeople)
			fatal("Too many nodes with people (%u max)", MaxPeople);
		npeople++;
	}
}

void Graph::addedge(int src, int dst, double cost) {
	adj[src*nodes.size()+dst] = cost;
	adj[dst*nodes.size()+src] = cost;
	nodes[src].out.push_back(dst);
	nodes[dst].out.push_back(src);
}

void Graph::addperson(int n) {
	if (nodes[n].p >= 0) {
		people[nodes[n].p].num++;
		return;
	}
	nodes[n].p = people.size();
	people.push_back(People(1, n));
}

Graph::Shortest::Shortest() :
	i(-1), dist(std::numeric_limits<double>::infinity()) {
}

void Graph::Shortest::setind(Shortest *s, long i) {
	s->i = i;
}

bool Graph::Shortest::pred(const Shortest *a, const Shortest *b) {
	return a->dist < b->dist;
}

void Graph::precompute(int n0) {
	if (shortest[n0].size() > 0)	// already computed.
		return;

	BinHeap<Shortest, Shortest*> open;

	std::vector<Shortest> closed(nodes.size());
	for (unsigned int i = 0; i < closed.size(); i++) {
		closed[i].i = -1;
		closed[i].parent = -1;
		closed[i].id = i;
		closed[i].dist = std::numeric_limits<double>::infinity();
	}

	closed[n0].dist = 0;
	open.push(&closed[n0]);

	while (!open.empty()) {
		auto n = *open.pop();
		const std::vector<int> &kids = nodes[n->id].out;

		for (auto i = kids.begin(); i != kids.end(); i++) {
			assert (*i >= 0);
			assert ((unsigned int) *i < closed.size());
			auto m = &closed[*i];
			double c = adj[n->id*nodes.size()+*i];

			if (m->dist <= n->dist + c)
				continue;

			m->dist = n->dist + c;
			m->parent = n->id;
			open.pushupdate(m, m->i);
		}
	}

	shortest[n0] = std::move(closed);
}

void Graph::init(unsigned int n) {
	nodes.resize(n);
	for (unsigned int i = 0; i < n; i++) {
		nodes[i].id = i;
		nodes[i].p = -1;
	}
	adj.resize(n*n, std::numeric_limits<double>::infinity());
	shortest.resize(n);
}